package com.cty.TestTemplate;

import org.junit.*;
import static org.junit.Assert.*;
import static org.hamcrest.Matchers.*;

/**
 * @Auther: cty
 * @Date: 2020/7/22 15:57
 * @Description: 测试模板——输入二叉树（普通二叉树和二叉搜索树都可以用）
 * **二叉树**
 *     * 特殊值测试：
 *         * null
 *     * 边界值测试：
 *         * 只有一个根节点
 *     * 功能测试：
 *         * 只有左节点
 *         * 只有右节点
 *         * 平衡树
 *         * 不平衡树
 * @version: 1.0
 */
public class _04_01_TestBinaryTree {

    @Test
    public void test(){
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
    }  // end test()

    void connectTreeNode(BinaryTreeNode parent, BinaryTreeNode leftChild, BinaryTreeNode rightChild){
        parent.leftChild = leftChild;
        parent.rightChild = rightChild;
    }  // end connectTreeNode()


    void test1(){
        // 一 测试特殊值
        // 空指针
        BinaryTreeNode node_null = null;
        //TODO: Test goes here...

        // 二 测试边界值
        // 只有一个节点
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        //TODO: Test goes here...

    }  // end test1()

    // 三 功能测试
    // 只有左节点
    //               5
    //              /
    //             4
    //            /
    //           3
    //          /
    //         2
    //        /
    //       1
    void test2(){
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        BinaryTreeNode n2 = new BinaryTreeNode(2);
        BinaryTreeNode n3 = new BinaryTreeNode(3);
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n5 = new BinaryTreeNode(5);

        connectTreeNode(n5,n4,null);
        connectTreeNode(n4,n3,null);
        connectTreeNode(n3,n2,null);
        connectTreeNode(n2,n1,null);

        //TODO: Test goes here...
        // treeRoot = n5
        
    }  // end test2

    // 只有右节点
    // 1
    //  \
    //   2
    //    \
    //     3
    //      \
    //       4
    //        \
    //         5
    void test3(){
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        BinaryTreeNode n2 = new BinaryTreeNode(2);
        BinaryTreeNode n3 = new BinaryTreeNode(3);
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n5 = new BinaryTreeNode(5);

        connectTreeNode(n1,null,n2);
        connectTreeNode(n2,null,n3);
        connectTreeNode(n3,null,n4);
        connectTreeNode(n4,null,n5);

        //TODO: Test goes here...
        // treeRoot = n1

    }  // end test3()

    // 完全二叉搜索树
    //            8
    //        6      9
    //      5   7  10  11
    void test4(){
        BinaryTreeNode n5 = new BinaryTreeNode(5);
        BinaryTreeNode n6 = new BinaryTreeNode(6);
        BinaryTreeNode n7 = new BinaryTreeNode(7);
        BinaryTreeNode n8 = new BinaryTreeNode(8);
        BinaryTreeNode n9 = new BinaryTreeNode(9);
        BinaryTreeNode n10 = new BinaryTreeNode(10);
        BinaryTreeNode n11 = new BinaryTreeNode(11);

        connectTreeNode(n8,n6,n9);
        connectTreeNode(n6,n5,n7);
        connectTreeNode(n9,n10,n11);

        //TODO: Test goes here...
        // treeRoot = n8

    }  // end test4()

    // 不完全二叉搜索树
    //            8
    //        6      9
    //      5   7  10  11
    //                    12
    void test5(){
        BinaryTreeNode n5 = new BinaryTreeNode(5);
        BinaryTreeNode n6 = new BinaryTreeNode(6);
        BinaryTreeNode n7 = new BinaryTreeNode(7);
        BinaryTreeNode n8 = new BinaryTreeNode(8);
        BinaryTreeNode n9 = new BinaryTreeNode(9);
        BinaryTreeNode n10 = new BinaryTreeNode(10);
        BinaryTreeNode n11 = new BinaryTreeNode(11);
        BinaryTreeNode n12 = new BinaryTreeNode(12);

        connectTreeNode(n8,n6,n9);
        connectTreeNode(n6,n5,n7);
        connectTreeNode(n9,n10,n11);
        connectTreeNode(n11,null,n12);

        //TODO: Test goes here...
        // treeRoot = n8

    }  // end test5()

    // 完全二叉树
    //            1
    //        2      3
    //      4   5  6   7
    void test6(){
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        BinaryTreeNode n2 = new BinaryTreeNode(2);
        BinaryTreeNode n3 = new BinaryTreeNode(3);
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n5 = new BinaryTreeNode(5);
        BinaryTreeNode n6 = new BinaryTreeNode(6);
        BinaryTreeNode n7 = new BinaryTreeNode(7);

        connectTreeNode(n1,n2,n3);
        connectTreeNode(n2,n4,n5);
        connectTreeNode(n3,n6,n7);

        //TODO: Test goes here...
        // treeRoot = n1

    }  // end test6()

    // 不完全二叉树
    //            1
    //        2      3
    //      4   5  6   7
    //                   8
    void test7(){
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        BinaryTreeNode n2 = new BinaryTreeNode(2);
        BinaryTreeNode n3 = new BinaryTreeNode(3);
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n5 = new BinaryTreeNode(5);
        BinaryTreeNode n6 = new BinaryTreeNode(6);
        BinaryTreeNode n7 = new BinaryTreeNode(7);
        BinaryTreeNode n8 = new BinaryTreeNode(8);

        connectTreeNode(n1,n2,n3);
        connectTreeNode(n2,n4,n5);
        connectTreeNode(n3,n6,n7);
        connectTreeNode(n7,null,n8);

        //TODO: Test goes here...
        // treeRoot = n1

    }  // end test7()

    class BinaryTreeNode {
        int value;
        BinaryTreeNode leftChild;
        BinaryTreeNode rightChild;

        public BinaryTreeNode(){}
        public BinaryTreeNode(int value){this.value = value;}
    }  // end class

}  // end class


